package solution;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.List;

public class BreadthFirstPathsTest {

    @Test
    @DisplayName("测试无权无向图的广度优先路径算法：是否存在从起点到终点的路径？")
    public void testHasPathToTarget(){
        //0: [1]
        //1: [0, 2, 4]
        //2: [1, 5]
        //3: [4]
        //4: [1, 3, 5]
        //5: [2, 4, 6, 8]
        //6: [5, 7]
        //7: [6]
        //8: [5]
        Graph<Integer> graph = new AdjacencyListGraph<>();
        graph.addEdge(0,1);
        graph.addEdge(1,2);
        graph.addEdge(1,4);
        graph.addEdge(2,5);
        graph.addEdge(3,4);
        graph.addEdge(4,5);
        graph.addEdge(4,5);
        graph.addEdge(5,6);
        graph.addEdge(5,8);
        graph.addEdge(6,7);

        BreadthFirstPaths<Integer> paths = new BreadthFirstPaths<>(graph, 0);
        Assertions.assertTrue(paths.hasPathTo(3));

    }

    @Test
    @DisplayName("测试无权无向图的广度优先路径算法：计算从起点到终点的路径")
    public void testPathToTarget(){
        //0: [1]
        //1: [0, 2, 4]
        //2: [1, 5]
        //3: [4]
        //4: [1, 3, 5]
        //5: [2, 4, 6, 8]
        //6: [5, 7]
        //7: [6]
        //8: [5]
        Graph<Integer> graph = new AdjacencyListGraph<>();
        graph.addEdge(0,1);
        graph.addEdge(1,2);
        graph.addEdge(1,4);
        graph.addEdge(2,5);
        graph.addEdge(3,4);
        graph.addEdge(4,5);
        graph.addEdge(4,5);
        graph.addEdge(5,6);
        graph.addEdge(5,8);
        graph.addEdge(6,7);

        BreadthFirstPaths<Integer> paths = new BreadthFirstPaths<>(graph, 0);
        Assertions.assertEquals(List.of(0, 1, 4, 5, 6, 7), paths.pathTo(7));
        Assertions.assertEquals(List.of(0, 1, 4, 3), paths.pathTo(3));

    }
}
